// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef CC_OUTPUT_BSP_TREE_H_
#define CC_OUTPUT_BSP_TREE_H_

#include <stddef.h>

#include <deque>
#include <memory>
#include <vector>

#include "cc/output/bsp_compare_result.h"
#include "cc/quads/draw_polygon.h"

namespace cc {

struct BspNode {
    // This represents the splitting plane.
    std::unique_ptr<DrawPolygon> node_data;
    // This represents any coplanar geometry we found while building the BSP.
    std::vector<std::unique_ptr<DrawPolygon>> coplanars_front;
    std::vector<std::unique_ptr<DrawPolygon>> coplanars_back;

    std::unique_ptr<BspNode> back_child;
    std::unique_ptr<BspNode> front_child;

    explicit BspNode(std::unique_ptr<DrawPolygon> data);
    ~BspNode();
};

class CC_EXPORT BspTree {
public:
    explicit BspTree(std::deque<std::unique_ptr<DrawPolygon>>* list);
    std::unique_ptr<BspNode>& root() { return root_; }

    template <typename ActionHandlerType>
    void TraverseWithActionHandler(ActionHandlerType* action_handler) const
    {
        if (root_) {
            WalkInOrderRecursion<ActionHandlerType>(action_handler, root_.get());
        }
    }

    ~BspTree();

private:
    std::unique_ptr<BspNode> root_;

    void FromList(std::vector<std::unique_ptr<DrawPolygon>>* list);
    void BuildTree(BspNode* node, std::deque<std::unique_ptr<DrawPolygon>>* data);

    template <typename ActionHandlerType>
    void WalkInOrderAction(ActionHandlerType* action_handler,
        DrawPolygon* item) const
    {
        (*action_handler)(item);
    }

    template <typename ActionHandlerType>
    void WalkInOrderVisitNodes(
        ActionHandlerType* action_handler,
        const BspNode* node,
        const BspNode* first_child,
        const BspNode* second_child,
        const std::vector<std::unique_ptr<DrawPolygon>>& first_coplanars,
        const std::vector<std::unique_ptr<DrawPolygon>>& second_coplanars) const
    {
        if (first_child) {
            WalkInOrderRecursion(action_handler, first_child);
        }
        for (size_t i = 0; i < first_coplanars.size(); i++) {
            WalkInOrderAction(action_handler, first_coplanars[i].get());
        }
        WalkInOrderAction(action_handler, node->node_data.get());
        for (size_t i = 0; i < second_coplanars.size(); i++) {
            WalkInOrderAction(action_handler, second_coplanars[i].get());
        }
        if (second_child) {
            WalkInOrderRecursion(action_handler, second_child);
        }
    }

    template <typename ActionHandlerType>
    void WalkInOrderRecursion(ActionHandlerType* action_handler,
        const BspNode* node) const
    {
        // If our view is in front of the the polygon
        // in this node then walk back then front.
        if (GetCameraPositionRelative(*(node->node_data)) == BSP_FRONT) {
            WalkInOrderVisitNodes<ActionHandlerType>(action_handler,
                node,
                node->back_child.get(),
                node->front_child.get(),
                node->coplanars_front,
                node->coplanars_back);
        } else {
            WalkInOrderVisitNodes<ActionHandlerType>(action_handler,
                node,
                node->front_child.get(),
                node->back_child.get(),
                node->coplanars_back,
                node->coplanars_front);
        }
    }

    // Returns whether or not our viewer is in front of or behind the plane
    // defined by this polygon/node
    static BspCompareResult GetCameraPositionRelative(const DrawPolygon& node);
};

} // namespace cc

#endif // CC_OUTPUT_BSP_TREE_H_
